/*
 * Created on 15 avr. 2005 by Tudor.Ionescu@supelec.fr
 */
package clustering.framework;

import java.util.ArrayList;
import java.util.Hashtable;

import clustering.testing.*;

/**
 * @author Tudor.Ionescu@supelec.fr
 * @
 */
public class QuartetTree{
    public int N = 0; // number of leafs (files)
    //public QNode n1 = null;
    //public QNode n2 = null;
    public QNode root = null;
    public double m = 0; // best score
    public double M = 0; // worst score
    public double St = 0; // tree score
    public QuartetTree(){
        // create a the root quartet
        //root = new QNode(-1,new QNode(-1,root,null,null),new QNode(-1,root,null,null),new QNode(-1,root,null,null));
        root = new QNode(-1,null,null,null,-1);
    }
    public static String newick2Xml(String newick){
    	String xml = "";
    	String leaf = "";
    	newick = newick.replaceAll("'\n'","");
    	newick = newick.replaceAll("' '","");
    	newick = newick.replaceAll("'\r'","");
    	int leafCount = 0;
    	ArrayList nodesAl = new ArrayList();
    	for(int i=0;i<newick.length();i++){
    		//char lastToken = newick.charAt(i-1);
    		char token = newick.charAt(i);
    		//char nextToken = newick.charAt(i+1);
    		if(token == '('){
    			xml += "<node id=\"-1\">";
    		}else if(token == ')'){
    			if(leaf.length() > 0){
    				xml += "<node id=\""+leaf+"\" />";
    				leaf = "";
    			}
    			xml += "</node>";
    		}else if(token == ','){
    			if(leaf.length() > 0){
    				xml += "<node id=\""+leaf+"\" />";
    				leaf = "";
    			}    			
    		}else if(token != ';' && token != '\''){
    			leaf += token;
    		}
    	}
    	return xml;
    }
    String xml = "";
    String treefile = "";
    public String toString(){
        xml = "";
        xml += "<node St=\""+St+"\" id=\"-1\">";
        writeSubtree(root.adj[0],root);
        writeSubtree(root.adj[1],root);
        writeSubtree(root.adj[2],root);
        xml += "</node>";
        return xml;
    }
    void writeSubtree(QNode qn, QNode referer){
        if(qn.label == -1){
            xml += "<node hash=\""+qn.hashCode()+"\" parent=\""+referer.hashCode()+"\" id=\"-1\">";
            for(int i=0;i<qn.adj.length;i++){
                if(qn.adj[i] != null && qn.adj[i] != referer){
                    writeSubtree(qn.adj[i],qn);
                }
            }
        	xml += "</node>";
        }else{
            xml += "<node hash=\""+qn.hashCode()+"\" parent=\""+referer.hashCode()+"\" id=\""+qn.label+"\"/>";
        }
    }
    int cob = 0, ccb = 0;
    String insertCommas(String treefile){
    	String out_tree = "";
    	for(int i=0;i<treefile.length()-1;i++){
    		out_tree += treefile.charAt(i);
    		char c1 = treefile.charAt(i);
    		char c2 = treefile.charAt(i+1);
    		if((c1 == ')' && c2 == '(')||
    				(c1 == ')' && c2 != ')' && c2 != ';')
					){
    			out_tree += ",";
    		}
    	}
    	out_tree += treefile.charAt(treefile.length()-1);
    	return out_tree;
    }
    String removeExtraBrackets(String treefile){
    	for(int i=N-1;i>=0;i--){
    		treefile = treefile.replaceAll("\\("+i+"\\)",""+i);
    		Debug.append(treefile);
    	}
    	return treefile;
    }
    public String toTreeFile(){
        cob = 0;
        ccb = 0;
        N=0;
    	treefile = "(";
        cob++;
        writeSubtreeFile(root.adj[0],root);
        //if(treefile.charAt(treefile.length()-1)!=',')treefile += ",";
        writeSubtreeFile(root.adj[1],root);
        //if(treefile.charAt(treefile.length()-1)!=',')treefile += ",";
        writeSubtreeFile(root.adj[2],root);
        treefile += ");";
        ccb++;
        return removeExtraBrackets(insertCommas(treefile));
    }
    
    void writeSubtreeFile(QNode qn, QNode referer){
        if(qn.label == -1){
        	treefile += "(";
        	cob++;
            for(int i=0;i<qn.adj.length;i++){
                if(qn.adj[i] != null && qn.adj[i] != referer){
                	writeSubtreeFile(qn.adj[i],qn);
                    //if(i<qn.adj.length-1){
                    //	 if(treefile.charAt(treefile.length()-1)!=',')treefile += ",";
                    //}
                }
            }
            treefile += ")";//:0.5";
        	ccb++;
        }else{
        	//double bl = (double)(1.0 / (qn.label + 1));
        	treefile += "(" + qn.label + ")"; // + ":" + bl;
        	N++;
        }
    }
    
    // for details about the implementation check out
    // http://ocw.mit.edu > Computer Science > Introduction to Algorithms - Fall 2001
    Hashtable D = new Hashtable();
	ArrayList Q = new ArrayList();
	ArrayList S = new ArrayList();
	
    public Hashtable Dijkstra(QNode start, QNode [] qNodes)
	{
    	D.clear();
    	Q.clear();
    	S.clear();
        for(int i=0;i<qNodes.length;i++)
		{
			if(qNodes[i] == start)D.put(start,new Integer(0));
			else D.put(qNodes[i],new Integer(Integer.MAX_VALUE));
			Q.add(qNodes[i]);
		}

		while(Q.size() > 0)
		{
			QNode u = ExtractMin(D,Q);
			S.add(u);
			for(int i=0;i<u.adj.length;i++){
			    if(u.adj[i] != null){
			        if(((Integer)D.get(u.adj[i])).intValue() > ((Integer)D.get(u)).intValue() + 1){
			            D.put(u.adj[i],new Integer(((Integer)D.get(u)).intValue() + 1));
			        }
			    }
			}
		}
		Hashtable htNodePath = new Hashtable();
		for(int k=0;k<qNodes.length;k++){
			if(qNodes[k].label == start.label || qNodes[k].label == -1)continue;
			QNode finish = qNodes[k];
			
			ArrayList ShortestPath = new ArrayList();
			QNode prev = finish;
			ArrayList S2 = (ArrayList)S.clone();
			while(prev != start)
			{
				ShortestPath.add(prev);
				S2.remove(prev);
				int min = Integer.MAX_VALUE;
				QNode new_prev = null;
				for(int i=0;i<S2.size();i++)
				{
					QNode s = (QNode)S2.get(i);
					if((s.adj[0] == prev || s.adj[1] == prev || s.adj[2] == prev) &&((Integer)D.get(s)).intValue() < min)
					{
						min = ((Integer)D.get(s)).intValue();
						new_prev = s;
					}
				}
				prev = new_prev;
			}
			ShortestPath.add(start);
			htNodePath.put(finish,ShortestPath);
		}
		return htNodePath;
	}
    
    ArrayList ShortestPath = new ArrayList();    
    public ArrayList Dijkstra(QNode start, QNode finish, QNode [] qNodes){
        if(start == finish)return new ArrayList();
        //Hashtable D = new Hashtable();
		//ArrayList Q = new ArrayList();
        D.clear();
    	Q.clear();
    	S.clear();
        
		for(int i=0;i<qNodes.length;i++)
		{
			if(qNodes[i] == start)D.put(start,new Integer(0));
			else D.put(qNodes[i],new Integer(Integer.MAX_VALUE));
			Q.add(qNodes[i]);
		}	
		
		//ArrayList S = new ArrayList();

		while(Q.size() > 0)
		{
			QNode u = ExtractMin(D,Q);
			S.add(u);
			for(int i=0;i<u.adj.length;i++){
			    if(u.adj[i] != null){
			        if(((Integer)D.get(u.adj[i])).intValue() > ((Integer)D.get(u)).intValue() + 1){
			            D.put(u.adj[i],new Integer(((Integer)D.get(u)).intValue() + 1));
			        }
			    }
			}
		}
	
		ShortestPath.clear();
		QNode prev = finish;
		while(prev != start)
		{
			ShortestPath.add(prev);
			S.remove(prev);
			int min = Integer.MAX_VALUE;
			QNode new_prev = null;
			for(int i=0;i<S.size();i++)
			{
				QNode s = (QNode)S.get(i);
				if((s.adj[0] == prev || s.adj[1] == prev || s.adj[2] == prev) && ((Integer)D.get(s)).intValue() < min)
				{
					min = ((Integer)D.get(s)).intValue();
					new_prev = s;
				}
			}
			prev = new_prev;
		}
		ShortestPath.add(start);
		return ShortestPath;
    }
	
	private QNode ExtractMin(Hashtable D, ArrayList Q)
	{
		int min = Integer.MAX_VALUE;
		QNode gn = (QNode)Q.get(0);
		for(int i=0;i<Q.size();i++)
		{
			if(((Integer)D.get((QNode)Q.get(i))).intValue() < min)
			{
				min = ((Integer)D.get((QNode)Q.get(i))).intValue();
				gn = (QNode)Q.get(i);
			}
		}
		Q.remove(gn);
		return gn;
	}		
}